package 力扣.排序.合并排序;

public class 数组中的逆序对offer51 {
    int cnt = 0;
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int N = nums.length;
        int[] t = new int[N];
        mSort(nums,0,N,t);
        return cnt;
    }

    private void mSort(int[] nums, int b, int e, int[] t) {
        if (b >= e){
            return;
        }
        if (b + 1 >= e){
            return;
        }
        int mid = b + ((e - b) >> 1);
        mSort(nums, b, mid, t);
        mSort(nums, mid, e, t);

        int i = b,j = mid,to = i;
        while (i < mid || j < e){
            if (j >= e || (i < mid && nums[i] <= nums[j])) {
                t[to++] = nums[i++];//仅仅添加这里 ：求解逆序对的数目
                cnt += (j - mid);
            }else{
                t[to++] = nums[j++];
//                cnt += i - b; // 求解顺序对的数目
            }
        }
        for (int k = b; k < e; k++) {
            nums[k] = t[k];
        }
    }
}
